package class10;

/**
 *
 * 图的表示: 邻接表法  邻接矩阵法
 * <-> 表示方向, 数值表示对应方向的权重
 * A 4<->3 C 6<->5 B 1<->1 D 7<->1 A
 *
 * 邻接表: 描述每个点及其的连接关系
 * 那么表示为:
 * A: C, D
 * B: C, D
 * C: A, B
 * D: B, A
 *
 * 邻接矩阵: 通过矩阵表示两点之间的距离(边的权重值), 如果没有连接通过正无穷表示(∞)
 * (邻接矩阵可以认为是全排列, 边连接情况不可能超过全排列)
 * 那么表示为:
 *   A  B  C  D
 *A  0  ∞  3  7
 *B  ∞  0  6  1
 *C  4  5  0  ∞
 *D  1  1  ∞  0
 *
 *
 * 也可以用下面方式表示一个图
 * 数组第一个数值表示权重, 数值第二个数字表示出发的点, 数值第三个数字表示结束的点
 *
 * [7, 0, 4]
 * [4, 0, 3]
 * [3, 1, 3]
 * [8, 2, 4]
 *
 * 注意:
 * 图表示的方法很多, 但是建议固定为当前结构, 其他结构通过适配方式处理即可
 * 类似 createGraph 实现转换
 *
 */
public class GraphGenerator {

	// matrix 所有的边
	// N*3 的矩阵
	// [weight, from节点上面的值，to节点上面的值]
	public static Graph createGraph(Integer[][] matrix) {
		Graph graph = new Graph();
		for (int i = 0; i < matrix.length; i++) { 
			// matrix[0][0], matrix[0][1]  matrix[0][2]
			Integer weight = matrix[i][0];
			Integer from = matrix[i][1];
			Integer to = matrix[i][2];
			//初始点集均为空, 不存在则根据来源点,到达点创建
			if (!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}
			if (!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}
			//获取Node, 并适配Node需要变化的信息
			Node fromNode = graph.nodes.get(from);
			Node toNode = graph.nodes.get(to);
			//边初始化
			Edge newEdge = new Edge(weight, fromNode, toNode);
			//点添加直接邻居点
			fromNode.nexts.add(toNode);
			//点增加出入度
			fromNode.out++;
			toNode.in++;
			//点增加边
			fromNode.edges.add(newEdge);
			//图增加边
			graph.edges.add(newEdge);
		}
		return graph;
	}

}
